package com.yequan.leetcode.recursion.generateParenthesis_22;

import java.util.ArrayList;
import java.util.List;

/**
 * //给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
 * //
 * // 例如，给出 n = 3，生成结果为：
 * //
 * // [
 * //  "((()))",
 * //  "(()())",
 * //  "(())()",
 * //  "()(())",
 * //  "()()()"
 * //]
 * //
 * // Related Topics 字符串 回溯算法
 *
 * @author : Administrator
 * @date : 2020/3/29
 */
public class GenerateParenthesis {

    public static void main(String[] args) {
        GenerateParenthesis generateParenthesis = new GenerateParenthesis();
        List<String> res = generateParenthesis.generateParenthesis(3);
        System.out.println(res);
    }

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(0, 0, n, res, "");
        return res;
    }

    /**
     * 递归循环增加括号法:
     * 1.相当于有 2n 个格子,往格子里填 '('或')',当填满格子时结束
     * 2.需要合法的括号对数: '('')'都不能超过n个,同时先填'('再填')',只有当')'个数小于'('时才能填')'
     *
     * @param left
     * @param right
     * @param max
     * @param res
     * @param s
     */
    private void helper(int left, int right, int max, List<String> res, String s) {
        //terminator
        if (left == max && right == max) {
            res.add(s);
            return;
        }
        //process current logic

        //drill down
        //新增左括号
        if (left < max) {
            helper(left + 1, right, max, res, s + "(");
        }
        //新增右括号
        if (left > right) {
            helper(left, right + 1, max, res, s + ")");
        }
        //reverse state
    }

}
